Number of digit one

Time: O(LogN); Space: O(1); hard

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

Example 1:

Input: num = 13

Output: 6

Explanation:

  • Digit 1 occurred in the following numbers:

  • 1, 10, 11, 12, 13

[1]:

class Solution1(object):
    def countDigitOne(self, num) -> int:
        """
        :type num: int
        :rtype: int
        """
        k = 1
        cnt, multiplier, left_part = 0, 1, num

        while left_part > 0:
            # split number into: left_part, curr, right_part
            curr = left_part % 10
            right_part = num % multiplier

            # count of (c000 ~ oooc000) = (ooo + (k < curr)? 1 : 0) * 1000
            cnt += (left_part // 10 + (k < curr)) * multiplier

            # if k == 0, oooc000 = (ooo - 1) * 1000
            if k == 0 and multiplier > 1:
                cnt -= multiplier

            # count of (oook000 ~ oookxxx): count += xxx + 1
            if curr == k:
                cnt += right_part + 1

            left_part //= 10
            multiplier *= 10

        return cnt

[2]:

s = Solution1()
num = 13
assert s.countDigitOne(num) == 6